package 剑指offer;

public class p10_2青蛙跳台阶问题 {

    public int numWays1(int n) {
        int a=1;
        int b=1;

        for (int i=0;i<n;i++) {
            int sum=(a+b)%1000000007;
            a=b;
            b=sum;
        }
        return a;

    }

    public int numWays(int n) {
        if (n==0) return 1;//当台阶为0时，有 1种 还是 0种 跳法，取决于平台
        if (n==1) return 1;//台阶为 1  1种跳法
        if (n==2) return 2;//台阶为 2  2种跳法

        int fn2=1;
        int fn1=2;
        int fn=0;

        for (int i = 3; i <=n; i++) {
            fn=(fn1+fn2)%1000000007;
            fn2=fn1;
            fn1=fn;
        }
        return fn;

    }

}
